package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangjy
 * @description 路径总和
 * @date 2025/4/18 9:08
 */
public class HasPathSum_112 {

    public static void main(String[] args) {
        HasPathSum_112 hasPathSum112 = new HasPathSum_112();

        TreeNode five = new TreeNode(5, null, null);
        TreeNode four = new TreeNode(4, null, null);
        TreeNode three = new TreeNode(3, null, null);
        TreeNode two = new TreeNode(2, four, five);
        TreeNode one = new TreeNode(1, two, three);

        System.out.println(hasPathSum112.hasPathSum2(one, 8));
    }

    /**
     * 参考官解：dfs-迭代
     *
     */
    public boolean hasPathSum3(TreeNode root, int targetSum) {
        if (root == null) return false;

        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> nodePathSum = new LinkedList<>();
        queue.offer(root);
        nodePathSum.offer(root.val);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            Integer pathSum = nodePathSum.poll();
            if (poll.left == null && poll.right == null && targetSum == pathSum) return true;

            if (poll.left != null) {
                queue.offer(poll.left);
                // 本层就记录孩子的路径和，是因为下一层一开始要判断路径和
                nodePathSum.offer(pathSum + poll.left.val);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
                nodePathSum.offer(pathSum + poll.right.val);
            }
        }

        return false;
    }

    /**
     * dmsxl：dfs-递归
     * <p>
     * 显示回溯；
     * 记录孩子节点值，判断孩子节点
     */
    public boolean hasPathSum2(TreeNode root, int targetSum) {
        if (root == null) return false;

        return dfs2(root, targetSum - root.val);
    }

    public boolean dfs2(TreeNode node, int targetSum) {
        // 叶子节点，且找到满足条件的路径和
        if (node.left == null && node.right == null && targetSum == 0) return true;
        // 叶子节点，但是未满足条件的路径和
        if (node.left == null && node.right == null) return false;

        // 显示回溯
        if (node.left != null) {
            targetSum -= node.left.val;
            boolean left = dfs2(node.left, targetSum);
            if (left) return true;
            targetSum += node.left.val;
        }
        if (node.right != null) {
            targetSum -= node.right.val;
            boolean right = dfs2(node.right, targetSum);
            if (right) return true;
            targetSum += node.right.val;
        }

        return false;
    }

    /**
     * 个解：dfs-递归
     * <p>
     * 隐藏回溯
     * 记录当前节点值 + 判断当前节点
     * <p>
     * 分析：
     * 1.找到一个满足targetSum的路径和就行，意味着找到就返回，不用进行后续递归操作。
     * 2.路径满足从root——>叶子。
     * 3.求路径和pathSum，它要等于targetSum，就是当targetSum减为0时，就找到了该路径和，但还需判断是否为叶子节点
     * 4.任一种遍历顺序都可以，因为这里没有对 中 的处理逻辑。
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return dfs(root, targetSum);
    }

    public boolean dfs(TreeNode node, int targetSum) {
        if (node == null) return false;

        // 隐藏回溯；因为只修改一次targetSum
        targetSum -= node.val;
        if (node.left == null && node.right == null) {
            return targetSum == 0;
        }

        boolean left = dfs(node.left, targetSum);
        if (left) return true;
        boolean right = dfs(node.right, targetSum);
        if (right) return true;

        return false;
    }

}
